原题链接:[UVA 1347] Tour
原题大意:一个图上有个点,给定他们的坐标.现在分别有两个人在最左端和最右端的点上移动,各个点的坐标都是不同的.两个人不能走到同一个点上,问走过的总距离最少是多少.
数据范围:
思路
显然让两个人从左边走到右边,又从右边走到左边是非常蛋疼的.不过由于距离是欧式距离是双向的,不妨把这个问题变成两个人同时从起点出发,且经过的点不重复的最小距离.这就很像一个网络流的模型,但是费用流做不了,或者说很难做,首先必须保证所有的点都经过了,其次边可能达到的级别,这是跑不了的.
现在来考虑DP,一个比较直接的想法就是表示第一个人走到了,第二个人走到了.入口出口都比较好想,但是没法转移:因为这个状态根本没有一个是否能走到下一个点的信息,假如现在要计算那这个点是否被用过了,根本不知道,没法转移.
既然如此,就把状态修改成这样:表示这些点都被经过了的前提下,两者位置分别是,剩余还要走的最小距离是多少.这个状态就可以解决掉之前的问题,即可以知道一个信息:这个点有没有被用过.在此基础上,减少一定的讨论,可以规定,这样就可以在不影响答案的前提下去减少一些讨论.不过这样还是不能转移,因为当前是的时候,如果直接走到这个点,显然这个点就走不了了,因为状态根本没法表示了,但是这个转移的时候又没有限制,这里有个很巧妙的想法:禁止这样的转移,每次转移就只能走到.为什么这样是正确的呢,因为当走到的时候,其实第二个人必须要走过这个点,不妨就让第二个人先转移到再让第一个人走到上,这个结果上是符合要求的,也不会出现一个点没有被用到的情况.
重新梳理一下过程:
状态:表示当前已经走过了这些点,并且.两者分别在这两点上时,剩余还要走的距离的所有集合里最小的具体值是多少.
入口:
转移:转移有两种,一种是从走到.这种情况下就是.另一种是第二个人走到,即注意这里本来是的,但是之前定义的时候要求保证所以调换了顺序.
出口:答案就是
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int n;
double x[N],y[N],f[N][N];
double gdist(int a,int b)
{
double dx = x[a] - x[b],dy = y[a] - y[b];
return sqrt(dx * dx + dy * dy);
}
int main()
{
while((scanf("%d",&n)) == 1)
{
for(int i = 1;i <= n;++i) scanf("%lf%lf",&x[i],&y[i]);
for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) f[i][j] = 1e10;
f[n][n - 1] = gdist(n,n - 1);
for(int i = n - 1;i >= 1;--i)
{
for(int j = i - 1;j >= 1;--j)
{
auto& v = f[i][j];
v = min(v,f[i + 1][j] + gdist(i,i + 1));
v = min(v,f[i + 1][i] + gdist(j,i + 1));
}
}
// cout << f[2][1] << endl;
printf("%.2lf\n",f[2][1] + gdist(1,2));
}
return 0;
}